/******************************************
Arbol_huffman.java
Universidad del Valle de Guatemala
Algoritmos y Estructura de Datos
Autor:
    Martín Guzmán
Fecha: 15 de agosto de 2009
Descripción: Contiene la descripción de un
 * árbol de huffman. En esta clase se genera
 * el árbol y se busca el código de determinado
 * carácter
*******************************************/
import java.util.ArrayList;
import java.lang.reflect.Array;
import java.lang.AssertionError;

public class Arbol_huffman {
    Nodo<String> padre;
    ArrayList<Simbolo> lista= new ArrayList<Simbolo>();
    private ArrayList<Simbolo> lista_caracteres= new ArrayList<Simbolo>();


    //método constructor
    public Arbol_huffman(){
        padre= new Nodo("");
    }

    //método para generar el arbol de huffman
    public void Generar_arbol(Lista_ordenada lista1){
        this.lista=lista1.getLista();//se obtiene lista ordenada

        //guarda en una lista todos los caracteres que tiene la lista enviada
        for(int i=0;i<this.lista.size();i++){
            getLista_caracteres().add(this.lista.get(i));
        }

        //se guarda en el padre el primer elemento de la lista ordenada
        this.padre.setNombre(this.lista.get(0).getNombre());
        //System.out.println("nombre: "+padre.getNombre());//Prueba
        this.lista.remove(0);//se borra dicho primer elemento

        //termina cuando se terminaron los padres a poner
        while(lista.size()!=0)
        {
            Nodo temporal_izq= new Nodo(lista.get(0).getNombre());
            Nodo temporal_der= new Nodo("");
            lista.remove(0);
            
            temporal_der.setHijo_derecho(padre.getHijo_derecho());//******** con esto evito crear áliases
            temporal_der.setHijo_izquierdo(padre.getHijo_izquierdo());//******** con esto evito crear áliases
            temporal_der.setNombre(padre.getNombre());//******** con esto evito crear áliases

            this.padre.setHijo_derecho(temporal_der);
            this.padre.setHijo_izquierdo(temporal_izq);
            this.padre.setNombre(""+padre.getHijo_izquierdo().getNombre()+""+padre.getHijo_derecho().getNombre());

        }
        //System.out.println("Nombre del padre: "+padre.getNombre()+" Hijo der: "+padre.getHijo_derecho()+" Hijo izq: "+padre.getHijo_izquierdo());//TODO quitar esto
    }

    public boolean Se_encuentra_en(String comparacion, Nodo hijo){

        String nombre_temporal = hijo.toString();//el toString() del nodo es su nombre
        for(int i=0;i<nombre_temporal.length();i++)
        {
            if(nombre_temporal.charAt(i)==comparacion.charAt(0))
            {
                //System.out.println("True");//Prueba
                return true;
            }
        }
        //System.out.println("False");//Prueba
        return false;
    }


    public String Obtener_valor(String letra){
        Nodo temporal = new Nodo("");
        String cadena="";
        temporal.setHijo_derecho(padre.getHijo_derecho()); //******** con esto evito crear áliases
        temporal.setHijo_izquierdo(padre.getHijo_izquierdo());//******** con esto evito crear áliases
        temporal.setNombre(padre.getNombre());//******** con esto evito crear áliases
        do
        {
            //System.out.println("Analizando letra: "+letra+" ****** >> Nombre del padre: "+temporal.getNombre()+" Hijo der: "+temporal.getHijo_derecho()+" Hijo izq: "+temporal.getHijo_izquierdo());//TODO quitar esto
            
            // Si toma el camino derecho, tiene que repetir el ciclo a partir del hijo derecho del actual
            if((Se_encuentra_en(letra,temporal.getHijo_derecho())) ){
                cadena+="1";

                //Se copian las caracteríasticas del hijo derecho
                Nodo temporal2 = new Nodo("");

                temporal2.setHijo_derecho(temporal.getHijo_derecho());//******** con esto evito crear áliases
                temporal2.setHijo_izquierdo(temporal.getHijo_izquierdo());//******** con esto evito crear áliases
                temporal2.setNombre(temporal.getHijo_derecho().getNombre());//******** con esto evito crear áliases

                //System.out.println("temporal2.getHijo_derecho()"+temporal2.getHijo_derecho());//Prueba
                //System.out.println("temporal2.getHijo_izquierdo()"+temporal2.getHijo_izquierdo());//Prueba

                temporal.setHijo_derecho(temporal2.getHijo_derecho().getHijo_derecho());
                temporal.setHijo_izquierdo(temporal2.getHijo_derecho().getHijo_izquierdo());
                temporal.setNombre(temporal2.getHijo_derecho().getNombre());

                //para revisar cuando parar
                if(temporal.getHijo_derecho()==null){
                    break;
                }
            }
            else if((Se_encuentra_en(letra,temporal.getHijo_izquierdo())) ){
                cadena+="0";
                //si toma por el camino izquierdo significa que ya llegó al destino
                break;
            }
        } while(true);
        return cadena;//regresa la cadena que se va formando
    }

    public ArrayList<Simbolo> getLista_caracteres() {
        return lista_caracteres;
    }
}